/*
https://leetcode-cn.com/problems/number-of-ways-to-reconstruct-a-tree/solution/zhong-gou-yi-ke-shu-de-fang-an-shu-by-le-36e1/
 */
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution1719 {
    public int checkWays(int[][] pairs) {
        Map<Integer, Set<Integer>> map=new HashMap<>();
        for (int[] pair : pairs) {
            map.putIfAbsent(pair[0],new HashSet<>());
            map.putIfAbsent(pair[1],new HashSet<>());
            map.get(pair[0]).add(pair[1]);
            map.get(pair[1]).add(pair[0]);
        }
        int root=-1;
        for (Map.Entry<Integer, Set<Integer>> integerSetEntry : map.entrySet()) {
            if (integerSetEntry.getValue().size()==map.size()-1){
                root=integerSetEntry.getKey();
            }
        }
        if (root==-1){
            return 0;
        }
        int res=1;
        for (Map.Entry<Integer, Set<Integer>> integerSetEntry : map.entrySet()) {
            if (integerSetEntry.getKey()==root){
                continue;
            }
            int max=Integer.MAX_VALUE;
            int parent=-1;
            for (Integer integer : integerSetEntry.getValue()) {
                if (map.get(integer).size()<max && map.get(integer).size()>=integerSetEntry.getValue().size()){
                    parent=integer;
                    max=map.get(integer).size();
                }
            }
            if (parent==-1){
                return 0;
            }
            for (Integer integer : integerSetEntry.getValue()) {
                if (integer!=parent && !map.get(parent).contains(integer)){
                    return 0;
                }
            }
            if (map.get(parent).size()==integerSetEntry.getValue().size()){
                res=2;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1719().checkWays(new int[][]{{1,2},{2,3}}));
    }
}
